package DynamicProgramming;

public class _413_ArithmeticSlices {
    //solution 1:bruce forced
    public int numberOfArithmeticSlices_1(int[] A) {
        if (A.length < 3) {
            return 0;
        }
        int interval = 3;
        int length = A.length;
        int res = 0;
        while (interval <= length) {
            for (int i = 0; i <= length - interval; i++) {
                boolean arith = true;
                int temp = A[i + 1] - A[i];
                for (int j = i + 1; j < i + interval - 1; j++) {
                    if (A[j + 1] - A[j] != temp) {
                        arith = false;
                        break;
                    }
                }
                if (arith) {
                    res++;
                }
            }
            interval++;
        }
        return res;
    }
    //reference solution
    //hint: why inc + 1 + helper while sum has already + inc?
    //int inc = 1 +helper(),the 1 means this time satisfy the 3 number's arithmetic,
    //the helper() means how many number can the origin 3 number be added to make arithmetic slice with higher quantity of numbers.
    int sum = 0;
    public int numberOfArithmeticSlices(int[] A) {
        helper(A, A.length - 1);
        return sum;
    }

    public int helper(int[] A, int i) {
        if (i < 2) {
            return 0;
        }
        if (A[i - 1] - A[i] == A[i - 2] - A[i - 1]) {
            int inc = 1 + helper(A, i - 1);
            sum += inc;
            return inc;
        } else {
            helper(A, i - 1);
            return 0;
        }
    }
}
